package AVL;

import BST.ArvoreBinaria;
import BST.No;
import Util.Analisador;

public class AVLImpl implements AVL {

	private ArvoreBinaria BST = new ArvoreBinaria();
	
	@Override
	public String buscar(int elemento) {
		No noAchado = BST.procura(elemento);
		
		if(elemento <= 0)
			return "Parametro invalido";
		
		if(noAchado == null)
			return "Valor nao encontrado";
		
		
		return String.valueOf(factor(noAchado))+
		", "+String.valueOf(noAchado.getAltura());
	}
	
	
	
	@Override
	public String imprimeEmOrdem() {		
		return "["+this.BST.percorreEmOrdem().trim().replace(" ",", ")+"]";
	}

	//SEGUINDO O MESMO ESQUEMA DO ROTEIRO PASSADO
	@Override
	public String montarArvore(int[] numerosDaArvore) {
		
		if(!Util.Analisador.vetorValido(numerosDaArvore))
			return "Parametro invalido";
		
		for(int i = 0 ; i < numerosDaArvore.length ; i++)
			if(numerosDaArvore[i] > 0)
			      insere(numerosDaArvore[i]);
		
		return null;
	}
	
	/**
	 * Insere um elemento na arvore
	 * @param elemento a ser inserido
	 * @return true insercao com sucesso
	 *         false caso contrario
	 */
	private boolean insere(int elemento){
		
		No noInserido = BST.insere(elemento);
		
		rebalance(noInserido);
		
		return true;
	}
	
	/**
	 * Balancea a arvore
	 * @param noInserido no a qual a partir deste a arvore sera balanceada
	 * @return tipo de rotacao executada
	 */
	private String rebalance(No noInserido){
		String operacoes = "";
		
		No noRaiz = modificaAltura(noInserido);		
		
		while(noRaiz != null && !estaBalanceado(noRaiz)){	
			
			operacoes += restrutura(noRaiz);
			noRaiz = noRaiz.getAntecessor().getAntecessor();	
		}		
		
		return "";
	}
	
	
	/**
	 * Reestrutura a arvore
	 * @param avo raiz a partir da qual sera estruturada a arvore
	 * @return a operacao realizada
	 */
	private String restrutura(No avo){
		No pai;
		No filho;		
		String tipoRotacao = "";
		//encontra o pai
		if(alturaMaiorFilho(avo) == avo.getDireita().getAltura())
			pai = avo.getDireita();
		else 
			pai = avo.getEsquerda();
		
		//encontra o filho
		if(alturaMaiorFilho(pai) == pai.getDireita().getAltura())
			filho = pai.getDireita();
		else 
			filho = pai.getEsquerda();
		
		
		
		if(avo.getElemento() >  pai.getElemento()){				
			
			//ROTACAO SIMPLES
			if(pai.getElemento() > filho.getElemento()){
				rotaciona(pai,avo,"RIGHT");
				 tipoRotacao = "ROT_SIMPLES";
			
			}
			//DUPLA ROTACAO
			else{
				tipoRotacao = "ROT_DUPLA";
				rotaciona(filho,pai,"LEFT");
				rotaciona(filho,avo,"LEFT");
			}
		}
		
		else{	
			//ROTACAO SIMPLES
			if(pai.getElemento() < filho.getElemento()){
				rotaciona(pai,avo,"LEFT");
				 tipoRotacao = "ROT_SIMPLES";
			
			}
			//DUPLA ROTACAO
			else{
				tipoRotacao = "ROT_DUPLA";
				rotaciona(filho,pai,"LEFT");
				rotaciona(filho,avo,"LEFT");
			}
			
		}
					
		
		return "["+filho.getElemento()+"] "+tipoRotacao+"("+
					filho.getElemento()+", "+pai.getElemento()+", "+
					avo.getElemento()+")";
	}
	/**
	 * Modifica a altura apos a insercao
	 * @param no o no filho a ser modificado seus ancestrais
	 * @return o No desbalanceado
	 *         null caso a arvore esteja balanceada
	 */
	private No modificaAltura(No no){
		
		No iterator = no;
		
		while(iterator.getAntecessor() != null || estaBalanceado(iterator)){
			iterator = iterator.getAntecessor();
			iterator.setAltura(alturaMaiorFilho(iterator) + 1);
		}
		
		return iterator;
	}
	
	/**
	 * Retorna a altura do maior filho
	 * @param pai o nodo pai
	 * @return a altura do maior filho
	 */
	private int alturaMaiorFilho(No pai){
		
		int alturaFilhoDireito = pai.getDireita() == null ?
				0 : pai.getDireita().getAltura();
		
		int alturaFilhoEsquerdo = pai.getEsquerda() == null ?
				0 : pai.getEsquerda().getAltura(); 
		
		return alturaFilhoDireito > alturaFilhoEsquerdo ? 
				alturaFilhoDireito : alturaFilhoEsquerdo;
		
	}

	/**
	 * Verifica se o no esta balanceado
	 * @param no no a serverificado
	 * @return true caso o no esteja balanceado
	 *         false caso contrario
	 */
    private boolean estaBalanceado(No no){
    	return Math.abs(factor(no)) <= 1;
    }
    
    /**
	 * Retorna o fator de balanceamento do No
	 * @param no o no a ser verificado
	 * @return o fator de balanceamento
	 */
	//altura da esquerda - altura da direita
	private int factor(No no){		
		
		int alturaFilhoEsquerdo=0;
		int alturaFilhoDireito=0;
		
		if(no == null)
			return 0;
		
		if(no.getEsquerda() == null)
			alturaFilhoEsquerdo = 0;
		else
			alturaFilhoEsquerdo = no.getEsquerda().getAltura();
		
		if(no.getDireita() == null)
			alturaFilhoDireito = 0;
		else
			alturaFilhoDireito = no.getDireita().getAltura();
		
		
		return alturaFilhoEsquerdo - alturaFilhoDireito;
	}
	
	/**
	 * Verifica o tipo de operacao a ser utilizado
	 * 
	 * @param no
	 *            a ser realizado o splay
	 * @return  'Nothing'     : nenhuma operacao 
	 *          'ROT_SIMPLES' : operacao ROTACAO SIMPLES
	 *          'ROT_DUPLA'   : operacao ROTACAO DUPLA
	 */
	private String verificaOperacaoAVL(No no) {

		No pai = no.getAntecessor();

		// nao executa nenhuma operacao pois so tem um nodo
		if (pai == null)
			return "Nothing";

		No avo = pai.getAntecessor();

		
		//ROTACAO SIMPLES
		if (no.getElemento() < pai.getElemento()
				&& pai.getElemento() < avo.getElemento())
			return "ROT_SIMPLES-RIGHT";

		if (no.getElemento() > pai.getElemento()
				&& no.getElemento() > avo.getElemento())
			return "ROT_SIMPLES-LEFT";

		//ROTACAO DUPLA
		if (no.getAntecessor().getElemento() < no.getElemento())
			return "ROT_DUPLA-LEFT";

		return "ROT_DUPLA-RIGHT";

	}
	
	/**
	 * Rotaciona dois nos
	 * filho passa a ser pai, pai passa a ser filho
	 * @param filho no filho
	 * @param pai no pai
	 * @param direcao direcao da rotacao
	 * @return o no filho ja rotacionado
	 */
	private No rotaciona(No filho, No pai, String direcao) {
		No T2;

		if (direcao.equals("RIGHT")) {
			T2 = filho.getDireita();
			filho.setDireita(pai);
			pai.setEsquerda(T2);
		}

		else {
			T2 = filho.getEsquerda();
			filho.setEsquerda(pai);
			pai.setDireita(T2);
		}

		if (T2 != null)
			T2.setAntecessor(pai);

		// conecta com a arvore superior
		filho.setAntecessor(pai.getAntecessor());

		pai.setAntecessor(filho);

		// seta a raiz
		if (filho.getAntecessor() == null)
			this.BST.setRaiz(filho);
		else {
			if (filho.getAntecessor().getElemento()< filho.getElemento())
				filho.getAntecessor().setDireita(filho);
			else
				filho.getAntecessor().setEsquerda(filho);
		}

		return filho;
	}
	
	@Override
	public String remover(int elemento) {
		// TODO Auto-generated method stub
		return null;
	}
	
		
	public static void main(String args[]){
		AVL avl = new AVLImpl();
		
		avl.montarArvore(new int[]{1,2,3});
		
	}

}
